package com.njupt.LinkTable;


/**
 * 19. 删除链表的倒数第 N 个结点
 *
 */
public class RemoveNthFromEnd {

    /**
     * 快慢指针法
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode HEAD = new ListNode(-1, head);

        ListNode pre = HEAD;
        ListNode rear = HEAD;
        //rear向前走n+1步
        while(n+1 != 0){
            rear = rear.next;
            n--;
        }
        //快慢指针移动
        while(rear != null){
            rear = rear.next;
            pre = pre.next;
        }
        //删除
        pre.next = pre.next.next;

        return HEAD.next;
    }

    public  void printList(ListNode head){
        ListNode p = head;
        while(p != null){
            System.out.print(p.val + " ");
            p = p.next;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
//        ListNode node1 = new ListNode(2);
//        ListNode node2 = new ListNode(3);
//        ListNode node3 = new ListNode(4);

//        head.next = node1; node1.next = node2;node2.next = node3;

        RemoveNthFromEnd test = new RemoveNthFromEnd();
        ListNode listNode = test.removeNthFromEnd(head, 1);
        test.printList(listNode);
    }
}
